﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution105
{
    public TreeNode BuildTree(int[] preorder, int[] inorder)//迭代法，这个方法好像不太对，结果不稳定，（有相同的元素的时候）而且后序遍历和层序遍历都是错的
    {

        Stack<TreeNode> stack = new Stack<TreeNode>();
        int inorder_index = 0;//遍历inorder
        TreeNode node =new TreeNode(preorder[0]);
        TreeNode root = node;
        stack.Push(root);

         
        for (int i = 1; i < preorder.Length; i++)
        {
            int stackTop=stack.Peek().val;
            //if (preorder[i] != inorder[inorder_index])//不是和preorder比，而是和栈里面的比，4和4比，而不是10和4比
            if (stackTop != inorder[inorder_index])//不是和preorder比，而是和栈里面的比
            {
                
               
                root.left = new TreeNode(preorder[i]);
                root = root.left;
                stack.Push(root);
            }
            else//说明遇到了右孩子
            {
                //开始出栈，出栈的都是左孩子，同时移动index
                while(stack.Count  > 0&& inorder[inorder_index]== stack.Peek().val)
                {
                    root=stack.Pop();
                    inorder_index++;
                }
                root.right = new TreeNode(preorder[i]);
                root = root.right;
                stack.Push(root);


            }

          

        }



        return node;

    }



    Dictionary<int, int> map = new Dictionary<int, int>();//key是inorder的值，value是inorder的index
    public TreeNode BuildTree2(int[] preorder, int[] inorder)//递归法
    {

        int len = preorder.Length;
        for (int i = 0; i < inorder.Length; i++)//方便找根的位置
        {

            map[inorder[i]] = i;


        }



        return myBuildTree(preorder, inorder, 0, len - 1, 0, len - 1);


    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right)

    {


        if (preorder_left > preorder_right)
        {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preorder_left]);//当前的根节点是先序遍历的第一个
                                                              //左孩子是中序遍历左边的，右孩子是右边的


        int inorder_root = map[preorder[preorder_left]];//1
        int leftLen = inorder_root - inorder_left;//1-0=1
                                                  //int rigntLen = inorder_right- inorder_root ;//4-1=3,用不到




        //左孩子递归

        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + leftLen, inorder_left, inorder_root - 1);


        //右孩子递归
        root.right = myBuildTree(preorder, inorder, preorder_left + leftLen + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
    public void preOreder(TreeNode root)
    {//先序


        if (root == null) return;

        Console.Write(root.val + "   ");
        preOreder(root.left);
        preOreder(root.right);
    }  public void postOreder(TreeNode root)
    {//后序


        if (root == null) return;


        postOreder(root.left);
        postOreder(root.right);
        Console.Write(root.val + "   ");
    }
    public void inOreder(TreeNode root)
    {//中序


        if (root == null) return;


        inOreder(root.left);
        Console.Write(root.val + "   ");
        inOreder(root.right);
    }
    //先序的迭代法，最难
    public void preOrederItera(TreeNode root)
    { 
    //先来个栈
    Stack<TreeNode> preorder = new Stack<TreeNode>();

        TreeNode cur = root;
        while (cur != null||preorder.Count>0)
        {
            while(cur != null)
            {
                preorder.Push(cur);//进栈
                Console.Write(cur.val + "   ");
                cur = cur.left;
            }

            cur = preorder.Pop();//回到父亲节点，开始走右边
            cur = cur.right;





        }


    
    }//中序的迭代法
    public void inOrederItera(TreeNode root)
    { 
    //先来个栈
    Stack<TreeNode> preorder = new Stack<TreeNode>();

        TreeNode cur = root;
        while (cur != null||preorder.Count>0)
        {
            while(cur != null)
            {
                preorder.Push(cur);//进栈
              
                cur = cur.left;
            }

            cur = preorder.Pop();//回到父亲节点，开始走右边
            Console.Write(cur.val + "   ");
            cur = cur.right;





        }


    
    }

    //层序遍历

  public void  levelOrder(TreeNode root)
    {
        //来个队伍
        List<TreeNode> level = new List<TreeNode>();
       
        TreeNode cur = root;
        level.Add(cur);
        while (level.Count >0)
        {
            //第一个出队
            cur = level[0];
            Console.Write(cur.val + "   ");
            level.Remove(cur);//移除第一个
            if (cur.left != null)
            {
                level.Add(cur.left);
            }
            if(cur.right != null)
            {
                level.Add(cur.right);
            }

            //level.Remove(cur);//移除第一个
        }



    }
    public void LevelOrder(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            TreeNode cur = queue.Dequeue();
            Console.Write(cur.val + "   ");

            if (cur.left != null)
            {
                queue.Enqueue(cur.left);
            }
            if (cur.right != null)
            {
                queue.Enqueue(cur.right);
            }
        }
    }
}
class Program105
{

    static void Main105(string[] args)
    {


        Solution105 solution = new Solution105();
        int[] preorder = { 3, 9, 20, 15, 7 };
        int[] inorder = { 9, 3, 15, 20, 7 };
        TreeNode root = solution.BuildTree2(preorder, inorder);
        //遍历一下，看结果对不对
        
        solution.preOreder(root); Console.WriteLine("先序遍历");
        
        solution.inOreder(root); Console.WriteLine("中序遍历");
        solution.postOreder(root); Console.WriteLine("后序遍历");
        solution.preOrederItera(root); Console.WriteLine("先序的迭代法");
        
        solution.inOrederItera(root); Console.WriteLine("中序的迭代法"); 
        solution.levelOrder(root); Console.WriteLine("层序遍历");
        //preOreder

    }


}
